/**
https://leetcode.cn/problems/01-matrix/description/
 542. 01 矩阵
 Medium, 方钊堉 2024.12.07
 BFS
 */

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int rows = mat.size();
        int cols = mat[0].size();
        // 四个方向的移动：右、下、左、上
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};

        // 初始化结果矩阵和访问标记矩阵
        vector<vector<int>> dist(rows, vector<int>(cols, 0));
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));

        // 队列用于BFS遍历
        queue<pair<int, int>> q;

        // 将所有0的位置加入队列，并初始化结果矩阵和访问标记
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (mat[i][j] == 0) {
                    q.emplace(i, j);
                    visited[i][j] = true;
                }
            }
        }

        // 开始BFS遍历
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            // 尝试四个方向的移动
            for (int k = 0; k < 4; ++k) {
                int newX = x + dx[k];
                int newY = y + dy[k];

                // 检查新位置是否在矩阵范围内且未访问过
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !visited[newX][newY]) {
                    dist[newX][newY] = dist[x][y] + 1;
                    q.emplace(newX, newY);
                    visited[newX][newY] = true;
                }
            }
        }

        return dist;
    }
};